//请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 
//
// 
//
// 示例 1: 
//
// 输入: "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
//
// 
//
// 提示： 
//
// 
// s.length <= 40000 
// 
//
// 注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-rep
//eating-characters/ 
// Related Topics 哈希表 双指针 Sliding Window 
// 👍 134 👎 0

package leetcode.editor.cn;

import sun.nio.cs.ext.MacArabic;

import java.util.HashMap;
import java.util.Map;

//Java：最长不含重复字符的子字符串
public class ZuiChangBuHanZhongFuZiFuDeZiZiFuChuanLcof{
    public static void main(String[] args) {
        Solution solution = new ZuiChangBuHanZhongFuZiFuDeZiZiFuChuanLcof().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //感觉也是一个动态规划的题目，涉及到选择，看最近的一个是否选择要
    //最左边的一个是否选择要（最左边和最右边发生冲突的时候），后面的是否可以构成更长的字符串
    public int lengthOfLongestSubstring(String s) {
        if ( s == null ){
            return 0;
        }
        //弄一个哈希表进行记录最近的一个相同字符的位置，从而计算其距离
        //动态规划，计算其最大位置
        Map<Character,Integer> sameCharIndexs = new HashMap<>();
        int temp = 0,answer = 0;
        for (int i = 0; i < s.length(); i++) {
            //这里的默认值只要是负数就可以了，证明这个数第一次出现，还没有相同的字符
            int charIndex = sameCharIndexs.getOrDefault( s.charAt( i ), -1 );
            //哈希表更新最近的相同字符的位置
            sameCharIndexs.put( s.charAt( i ), i );
            //动态规划的状态转移公式
            //dp[i-1] -> dp[i]
            if ( temp < i - charIndex ){
                temp =  temp + 1;
            }else {
                temp = i - charIndex;
            }
            //max( dp[i-1], dp[i] )
            answer = Math.max( answer,temp );
        }
        return answer;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
